package br.univap.aed.cenario1.sort;

import java.util.Vector;

import br.univap.aed.cenario1.utils.Registro;

public class QuickSortRegistro {

	private int comparacoes = 0;
	private int copias = 0;

	public Vector<Registro> partition(Vector<Registro> vetor, int pivo) {
		if (vetor.size() <= 1) {
			return vetor;
		}

		Vector<Registro> L = new Vector<Registro>();
		Vector<Registro> E = new Vector<Registro>();
		Vector<Registro> G = new Vector<Registro>();

		Registro x, y;

		x = vetor.remove(pivo);
		E.add(x);

		while (!vetor.isEmpty()) {
			y = vetor.remove(0);

			if (y.getChave() < x.getChave()) {
				L.add(y);
				comparacoes++;
			} else if (y.getChave() == x.getChave()) {
				E.add(y);
				comparacoes += 2;
			} else if (y.getChave() > x.getChave()) {
				G.add(y);
				comparacoes += 3;
			}
		}

		vetor = merge(partition(L, QuicksortInteiro.sortear(L.size() - 1)), E,
				partition(G, G.size() - 1));

		return vetor;
	}

	private Vector<Registro> merge(Vector<Registro> L, Vector<Registro> E,
			Vector<Registro> G) {

		Vector<Registro> v = new Vector<Registro>();

		while (!L.isEmpty()) {
			v.add(L.remove(0));
		}

		while (!E.isEmpty()) {
			v.add(E.remove(0));
		}

		while (!G.isEmpty()) {
			v.add(G.remove(0));
		}

		copias++;
		return v;
	}

	public int getComparacoes() {
		return this.comparacoes;
	}

	public int getCopias() {
		return this.copias;
	}

}
